/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/two-sum-iv-input-is-a-bst
   @Language: C++
   @Datetime: 19-06-19 11:20
   */

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


// Method 1, hash, Time O(2n), Space O(n), Time 285ms
class Solution {
	void inorder(TreeNode *root, unordered_set<int> &hash){
		if(root==NULL) return;
		inorder(root->left,hash);
		hash.insert(root->val);
		inorder(root->right,hash);
	}
public:
	/*
	 * @param : the root of tree
	 * @param : the target sum
	 * @return: two number from tree witch sum is n
	 */
	vector<int> twoSum(TreeNode * root, int n) {
		// write your code here
		unordered_set<int> hash;
		inorder(root, hash);
		for(auto i=hash.begin(); i!=hash.end(); ++i){
			auto j=hash.find(n-(*i));
			if(j!=i && j!=hash.end()) return {*i,*j};
		}
		return {};
	}
};

// Method 2, two pointer, Time O(2n), Space O(n), Time 282ms
class Solution {
	void inorder(TreeNode *root, vector<int> &vs){
		if(root==NULL) return;
		inorder(root->left,vs);
		vs.push_back(root->val);
		inorder(root->right,vs);
	}
public:
	/*
	 * @param : the root of tree
	 * @param : the target sum
	 * @return: two number from tree witch sum is n
	 */
	vector<int> twoSum(TreeNode * root, int n) {
		// write your code here
		vector<int> vs;
		inorder(root, vs);
		for(int i=0, j=vs.size()-1; i<j;){
			const int sum=vs[i]+vs[j];
			if(sum==n) return {vs[i],vs[j]};
			if(sum>n) --j;
			else ++i;
		}
		return {};
	}
};

// Method 3, Binary Tree Iterator, Time O(n+h), Space O(h), Time 328ms
class Solution {
	class InorderIterator{
		stack<TreeNode*> s;
		bool forward;
		void prepose(TreeNode *root){
			for(; root; root=forward?root->left:root->right)
				s.push(root);
		}
	public:
		InorderIterator(TreeNode *root, bool forward){
			this->forward=forward;
			prepose(root);
		}
		TreeNode *next(){
			if(s.size()==0) return NULL;
			TreeNode *ans=s.top();
			s.pop();
			prepose(forward?ans->right:ans->left);
			return ans;
		}
	};
public:
	/*
	 * @param : the root of tree
	 * @param : the target sum
	 * @return: two number from tree witch sum is n
	 */
	vector<int> twoSum(TreeNode * root, int n) {
		// write your code here
		InorderIterator f(root,true), b(root,false);
		for(TreeNode *left=f.next(), *right=b.next(); left!=right;){
			const int sum=left->val+right->val;
			if(sum==n) return {left->val,right->val};
			if(sum>n) right=b.next();
			else left=f.next();
		}
		return {};
	}
};

// Method 4, prenode+nextnode, Time O(n*h), Space O(1), Time 56ms
class Solution {
	TreeNode* prenode(TreeNode *root, TreeNode *target){
		TreeNode *pre=NULL;
		for(; root && root!=target;){
			if(root->val<target->val){
				pre=root;
				root=root->right;
			}
			else root=root->left;
		}
		if(root==NULL) return NULL;
		if(root->left==NULL) return pre;
		for(root=root->left; root->right; root=root->right);
		return root;
	}
	TreeNode* nextnode(TreeNode *root, TreeNode *target){
		TreeNode *next=NULL;
		for(; root && root!=target;){
			if(root->val<target->val) root=root->right;
			else{
				next=root;
				root=root->left;
			}
		}
		if(root==NULL) return NULL;
		if(root->right==NULL) return next;
		for(root=root->right; root->left; root=root->left);
		return root;
	}
public:
	/*
	 * @param : the root of tree
	 * @param : the target sum
	 * @return: two number from tree witch sum is n
	 */
	vector<int> twoSum(TreeNode * root, int n) {
		// write your code here
		if(root==NULL) return {};
		TreeNode *left, *right;
		for(left=root; left->left; left=left->left);
		for(right=root; right->right; right=right->right);
		for(int sum=0; left!=right;){
			sum=left->val+right->val;
			if(sum==n) return {left->val,right->val};
			if(sum>n) right=prenode(root,right);
			else left=nextnode(root,left);
		}
		return {};
	}
};
